package com.dbh.alg.datastructure;

import java.util.ArrayList;
import java.util.List;

/**
 * @desc 排序链表
 * @author 董帮辉
 * @date 2025/5/11
 **/
public class E15Leetcode148 {

    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        List<ListNode> lists = new ArrayList<>();
        while (head != null) {
            lists.add(new ListNode(head.val));
            head = head.next;
        }
        return split(lists, 0, lists.size() - 1);
    }

    public static ListNode split(List<ListNode> lists, int i, int j) {
        if (i == j) {
            return lists.get(i);
        }
        int m = (i + j) >>> 1;
        ListNode left = split(lists, i, m);
        ListNode right = split(lists, m + 1, j);
        return mergeTwoListNode(left, right);
    }

    public static ListNode mergeTwoListNode(ListNode p1, ListNode p2) {
        if (p1 == null) {
            return p2;
        }
        if (p2 == null) {
            return p1;
        }
        if(p1.val < p2.val) {
            p1.next = mergeTwoListNode(p1.next, p2);
            return p1;
        } else {
            p2.next = mergeTwoListNode(p1, p2.next);
            return p2;
        }
    }

    public static void main(String[] args) {
        ListNode o = ListNode.of(-1,5,3,4,0);
        System.out.println(sortList(o));

    }
}
